package com.mxw.算法之美.a6排序;

/**
 * @author Administrator
 * @create 2024/7/24 15:51
 */
public class a04MergeSort {
    /**
     分治思想：
     先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，最后合并起来。

     递推公式：merge_Sort(p...r) = merge(merge_Sort(p...q), merge_Sort(q+1,r))
     递归终止条件：p >= r


     申请一个临时数组temp,大小与nums的长度一样。用两个游标i和j，分别指向nums[p...q],nums[q+1,r]的第一个元素
     比较nums[i]和nums[j]的大小，如果nums[i]<=nums[j],将nums[i]元素放入temp中，并且i后移动一位，否则将nums[j]元素放入temp中，并且j后移动一位。
     直到其中一个子数组的所有数据放入临时数组中。再把另一个数组的数据一次加入到临时数组的末尾

     原地排序：空间复杂度O(nlogN)
     稳定排序：相同大小的数据在排序前后不会改变顺序
     时间复杂度：O(nlogN)
     */


    private static int[] temp;

    private static void sort(int[] nums, int left, int right) {
        if (left == right) {
            // 单个元素不用排序
            return;
        }
        // 这样写是为了防止溢出，效果等同于 (hi + lo) / 2
        int mid = left + (right - left) / 2;

        // 先对左半部分数组 nums[lo..mid] 排序
        sort(nums, left, mid);
        // 再对右半部分数组 nums[mid+1..hi] 排序
        sort(nums, mid + 1, right);
        // 将两部分有序数组合并成一个有序数组
        // 2367,45910=>2345678910
        merge(nums, left, mid, right);
    }

    // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
    private static void merge(int[] nums, int left, int mid, int right) {
        // 先把 nums[lo..hi] 复制到辅助数组中
        // 以便合并后的结果能够直接存入 nums
        // (0,1),(0,2),(3,4),(0,4),(5,6),(7,8),(5,8),(0,8)
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        // 数组双指针技巧，合并两个有序数组
        int i = left, j = mid + 1;
        for (int index = left; index <= right; index++) {
            if (i == mid + 1) {
                // 左半边数组已全部被合并
                nums[index] = temp[j++];
            } else if (j == right + 1) {
                // 右半边数组已全部被合并
                nums[index] = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums[index] = temp[j++];
            } else {
                nums[index] = temp[i++];
            }
        }
    }
}

